package map;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
//todo use deque + map
public class AllOoneDataStructure432 {
    TreeMap<String, Integer> map ;

    public AllOoneDataStructure432() {
        map =  new TreeMap<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return map.get(o1) - map.get(o2);
            }
        });
    }

    public void inc(String key) {
        Integer time = map.getOrDefault(key, 0);
        map.put(key,time+1);
    }

    public void dec(String key) {
        Integer time = map.get(key);
        if(time ==1){
            map.remove(key);
        }else {
            map.put(key,time-1);
        }
    }

    public String getMaxKey() {
        if(map.size()!=0){
            return map.lastKey();
        }
        return "";
    }

    public String getMinKey() {
        if(map.size()!=0){
            return map.firstKey();
        }
        return "";
    }

}
